home *** CD-ROM | disk | FTP | other *** search
/ Developer CD Series 1999 May: Tool Chest / Developer CD Series Tool Chest (Apple Computer)(May 1999).iso / Tool Chest / Development Kits / MPW etc / Miscellaneous / MPW p2c / p2cLibraries / PSets.c < prev    next >
Encoding:
C/C++ Source or Header  |  1997-01-29  |  5.7 KB  |  186 lines  |  [TEXT/MPS ]
  1. /*---------------------------------------------------------------------------*
  2.  |                                                                           |
  3.  |                   <<< PSets.c - Pascal set routines >>>                   |
  4.  |                                                                           |
  5.  |                    Copyright Apple Computer, Inc. 1994                      |
  6.  |                            All rights reserved.                           |
  7.  |                                                                           |
  8.  *---------------------------------------------------------------------------*/
  9.  
  10. /* 
  11.  
  12. This file provides support for Pascal sets with more than 32 elements.
  13. Note that sets are zero based.
  14.  
  15. This file defines the following routines:
  16.  
  17. PSet_Init(theSet, nbrWords)                                                - initialize a large set to the empty set
  18. PSet_Set(theSet, nbrWords, theElem)                                - "turn on" an element in a large set
  19. PSet_SetRange(theSet, nbrWords, elem1, elem2)            - "turn on" a range of elements in a large set
  20. PSet_Test(theSet, nbrWords, theElem)                            - test an element in a large set
  21. PSet_Eq(set1, set2, nbrWords)                                            - test two sets for equality
  22. PSet_Subset(set1, set2, nbrWords)                                    - tests if first set is a subset of the second
  23. PSet_Subset2(set1, set2)                                                    - tests if first small (<= 32 bit) set is a subset of the second
  24. PSet_Difference(*dest, *set1, *set2, nbrWords)        - assign difference of two sets to a destination set
  25. PSet_Intersection(*dest, *set1, *set2, nbrWords)    - assign intersection of two sets to a destination set
  26. PSet_Union(*dest, *set1, *set2, nbrWords)                    - assign union of two sets to a destination set
  27.     
  28. */
  29.  
  30. #include <Types.h>
  31. #include <Memory.h>
  32. #include <string.h>
  33.  
  34. #include "PSets.h"
  35.  
  36.  
  37. #define ElemsPerWord 16
  38.  
  39.  
  40. /*-----------------------------------------------------*
  41.  | PSet_Init - initialize a large set to the empty set |
  42.  *-----------------------------------------------------*/
  43.  
  44. void PSet_Init(unsigned short *theSet, short nbrWords)
  45. {
  46.     memset(theSet, 0, nbrWords * 2);
  47. }
  48.  
  49.  
  50. /*------------------------------------------------*
  51.  | PSet_Set - "turn on" an element in a large set |
  52.  *------------------------------------------------*/
  53.  
  54. void PSet_Set(unsigned short *theSet, short nbrWords, unsigned long theElem)
  55. {
  56.     short idx = (nbrWords - 1) - (theElem / ElemsPerWord);
  57.     theSet[idx] = theSet[idx] | 1 << (theElem % ElemsPerWord);
  58. }
  59.  
  60.  
  61. /*--------------------------------------------------------------*
  62.  | PSet_SetRange - "turn on" a range of elements in a large set |
  63.  *--------------------------------------------------------------*/
  64.  
  65. void PSet_SetRange(unsigned short *theSet, short nbrWords, unsigned long elem1, unsigned long elem2)
  66. {
  67.     short idx;
  68.  
  69.     while (elem1 <= elem2) {
  70.         idx = (nbrWords - 1) - (elem1 / ElemsPerWord);
  71.         theSet[idx] = theSet[idx] | 1 << (elem1 % ElemsPerWord);
  72.         ++elem1;
  73.     }
  74. }
  75.  
  76.  
  77. /*--------------------------------------------*
  78.  | PSet_Test - test an element in a large set |
  79.  *--------------------------------------------*/
  80.  
  81. Boolean PSet_Test(unsigned short *theSet, short nbrWords, unsigned long theElem)
  82. {
  83.     if ((theElem / ElemsPerWord) > nbrWords)
  84.         return false;
  85.     return (theSet[(nbrWords - 1) - (theElem / ElemsPerWord)] & 1 << (theElem % ElemsPerWord)) != 0;
  86. }
  87.  
  88.  
  89. /*--------------------------------------*
  90.  | PSet_Eq - test two sets for equality |
  91.  *--------------------------------------*/
  92.  
  93. Boolean PSet_Eq(unsigned short *set1, unsigned short *set2, short nbrWords)
  94. {
  95.     while (nbrWords) {
  96.         if (*set1++ != *set2++)
  97.             return false;
  98.         --nbrWords;
  99.     };
  100.     return true;
  101. }
  102.  
  103.  
  104. /*------------------------------------------------------------*
  105.  | PSet_Subset - tests if first set is a subset of the second |
  106.  *------------------------------------------------------------
  107.  
  108.     Note:  A <= B  ==>  A ^ (A & B) = 0
  109.                  ie, there is nothing in A that is not in both
  110. */
  111.  
  112. Boolean PSet_Subset(unsigned short *set1, unsigned short *set2, short nbrWords)
  113. {
  114.     short s1;
  115.     while (nbrWords) {
  116.         s1 = *set1++;
  117.         if (s1 ^ (s1 & *set2++) != 0)
  118.             return false;
  119.         --nbrWords;
  120.     };
  121.     return true;
  122. }
  123.  
  124.  
  125. /*-------------------------------------------------------------------------------*
  126.  | PSet_Subset2 - tests if first small (<= 32 bit) set is a subset of the second |
  127.  *-------------------------------------------------------------------------------*/
  128.  
  129. Boolean PSet_Subset2(unsigned long set1, unsigned long set2)
  130. {
  131.     return (set1 ^ (set1 & set2) == 0);
  132. }
  133.  
  134.  
  135. /*----------------------------------------------------------------------*
  136.  | PSet_Difference - assign difference of two sets to a destination set |
  137.  *----------------------------------------------------------------------*/
  138.  
  139. unsigned short *PSet_Difference(unsigned short *dest, unsigned short *set1, unsigned short *set2, short nbrWords)
  140. {
  141.     unsigned short *origDest = dest;
  142.     
  143.     while (nbrWords) {
  144.         *dest++ = *set1++ & ~*set2++;
  145.         --nbrWords;
  146.     };
  147.     
  148.     return origDest;
  149. }
  150.  
  151.  
  152. /*--------------------------------------------------------------------------*
  153.  | PSet_Intersection - assign intersection of two sets to a destination set |
  154.  *--------------------------------------------------------------------------*/
  155.  
  156. unsigned short *PSet_Intersection(unsigned short *dest, unsigned short *set1, unsigned short *set2, short nbrWords)
  157. {
  158.     unsigned short *origDest = dest;
  159.     
  160.     while (nbrWords) {
  161.         *dest++ = *set1++ & *set2++;
  162.         --nbrWords;
  163.     };
  164.     
  165.     return origDest;
  166. }
  167.  
  168.  
  169. /*------------------------------------------------------------*
  170.  | PSet_Union - assign union of two sets to a destination set |
  171.  *------------------------------------------------------------*/
  172.  
  173. unsigned short *PSet_Union(unsigned short *dest, unsigned short *set1, unsigned short *set2, short nbrWords)
  174. {
  175.     unsigned short *origDest = dest;
  176.     
  177.     while (nbrWords) {
  178.         *dest++ = *set1++ | *set2++;
  179.         --nbrWords;
  180.     };
  181.     
  182.     return origDest;
  183. }
  184.  
  185.  
  186.